//插入排序的平均时间复杂度和选择排序一样，不过插入的性能更好一些，虽然是同一个量级，但是其所用时间是选择排序的一半
//最好情况只需比较N-1次，最坏情况就要慢的多，因为交换的情况更多
//对于部分有序的数组，插入排序的时间复杂度是线性的，运行时间与逆序对个数线性相关
//算法大概就是，遍历数组中每一个位置，遍历过的是排序好的，未遍历的是未排序的
//然后对于未排序的正在遍历的那个数，如果左边的数比他大，那么二者交换
//如此遍历直到结束
public class InsertionSort extends Sort {
     public void MySort(Point data[])
     {
        for(int i=1;i<data.length;i++)
        {
            for(int j=0;j<i;j++)
            {
              if(data[i-j].compareTo(data[i-j-1])<0)
              {
                Exchange(data,i-j,i-j-1);
              }
              else
              {
                break;
              }
            }
        }
     }
    
}
